package com.cuz.daileetcode.前序中序后序Morris;

import com.cuz.daileetcode.utils.TreeNode;

import java.util.Stack;

public class All {

    public static void process(TreeNode node) {
        if (node == null) {
            return;
        }
        //如果在这里打印 代表前序遍历
        process(node.left);
        //如果在这里打印中序遍历
        process(node.right);
        //如果在这里打印 后序遍历
        System.out.println(node.val);
    }

    public static void process1(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stackMemory = new Stack<>();
        stackMemory.push(root);
        while (!stackMemory.isEmpty()) {
            TreeNode temp = stackMemory.pop();
            System.out.println(temp.val);
            if (temp.right != null) {
                stackMemory.push(temp.right);
            }
            if (temp.left != null) {
                stackMemory.push(temp.left);
            }
        }
    }

    public static void process2(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stackMemory = new Stack<>();
        do {
            while (root != null) {
                stackMemory.push(root);
                root = root.left;
            }
            if (!stackMemory.isEmpty()) {
                root = stackMemory.pop();
                System.out.println(root.val);
                root = root.right;
            }
        } while (!stackMemory.isEmpty() || root != null);
    }

    /****
     * 非递归后序遍历
     * @param root 树根节点
     */
    public static void process3(TreeNode root) {
        Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
        TreeNode node = root;
        TreeNode lastVisit = root;
        while (node != null || !treeNodeStack.isEmpty()) {
            while (node != null) {
                treeNodeStack.push(node);
                node = node.left;
            }
            //查看当前栈顶元素
            node = treeNodeStack.peek();
            //如果其右子树也为空，或者右子树已经访问
            //则可以直接输出当前节点的值
            if (node.right == null || node.right == lastVisit) {
                System.out.print(node.val + " ");
                treeNodeStack.pop();
                lastVisit = node;
                node = null;
            } else {
                //否则，继续遍历右子树
                node = node.right;
            }
        }
    }

    public static void morris(TreeNode node) {
        TreeNode currentNode = node;
        TreeNode mostRightNodeOfCur = null;
        while (currentNode != null) {
            //一开始初始化为左节点
            mostRightNodeOfCur = currentNode.left;
            if (mostRightNodeOfCur != null) {

                //如果存在右节点，右节点 指向的不是自己（指第一次来到此节点）
                //一直向右
                while (mostRightNodeOfCur.right != null && mostRightNodeOfCur.right != currentNode) {
                    mostRightNodeOfCur = mostRightNodeOfCur.right;
                }
                //此时mostRightNodeOfCur 是左子树的最右节点
                //如果最右节点的右为null 说明是第一次来到此节点
                if (mostRightNodeOfCur.right == null) {
                    //让最右的右节点指向上一层
                    mostRightNodeOfCur.right = currentNode;
                    //自己向左
                    currentNode = currentNode.left;
                    continue;
                } else {
                    //第二次来到 让最右指向空
                    mostRightNodeOfCur.right = null;
                }
            }
            currentNode = currentNode.right;
        }
    }

    public static void morrisPrePrint(TreeNode node) {
        TreeNode currentNode = node;
        TreeNode mostRightNodeOfCur = null;
        while (currentNode != null) {
            //一开始初始化为左节点
            mostRightNodeOfCur = currentNode.left;
            if (mostRightNodeOfCur != null) {

                //如果存在右节点，右节点 指向的不是自己（指第一次来到此节点）
                //一直向右
                while (mostRightNodeOfCur.right != null && mostRightNodeOfCur.right != currentNode) {
                    mostRightNodeOfCur = mostRightNodeOfCur.right;
                }
                //此时mostRightNodeOfCur 是左子树的最右节点
                //如果最右节点的右为null 说明是第一次来到此节点
                if (mostRightNodeOfCur.right == null) {
                    //这个节点有左树 说明可以到达两次，这是第一次到达 so 打印
                    System.out.print(currentNode.val + "\t");
                    //让最右的右节点指向上一层
                    mostRightNodeOfCur.right = currentNode;
                    //自己向左
                    currentNode = currentNode.left;
                    continue;
                } else {
                    //第二次来到 让最右指向空
                    mostRightNodeOfCur.right = null;
                }
            } else {
                //当前节点没有左树 ，说明只能到达一次 直接打印
                System.out.print(currentNode.val + "\t");
            }
            currentNode = currentNode.right;
        }
    }

    public static void morrisMidPrint(TreeNode node) {
        TreeNode currentNode = node;
        TreeNode mostRightNodeOfCur = null;
        while (currentNode != null) {
            //一开始初始化为左节点
            mostRightNodeOfCur = currentNode.left;
            if (mostRightNodeOfCur != null) {
                //如果存在右节点，右节点 指向的不是自己（指第一次来到此节点）
                //一直向右
                while (mostRightNodeOfCur.right != null && mostRightNodeOfCur.right != currentNode) {
                    mostRightNodeOfCur = mostRightNodeOfCur.right;
                }
                //此时mostRightNodeOfCur 是左子树的最右节点
                //如果最右节点的右为null 说明是第一次来到此节点
                if (mostRightNodeOfCur.right == null) {
                    //让最右的右节点指向上一层
                    mostRightNodeOfCur.right = currentNode;
                    //自己向左
                    currentNode = currentNode.left;
                    continue;
                } else {
                    //这个节点有左树 说明可以到达两次，这是第二次到达 so 打印
                    System.out.print(currentNode.val + "\t");
                    //第二次来到 让最右指向空
                    mostRightNodeOfCur.right = null;
                }
            } else {
                //当前节点没有左树 ，说明只能到达一次 直接打印
                System.out.print(currentNode.val + "\t");
            }
            currentNode = currentNode.right;
        }
    }

    public static void morrisPostPrint(TreeNode node) {
        TreeNode currentNode = node;
        TreeNode mostRightNodeOfCur = null;
        while (currentNode != null) {
            //一开始初始化为左节点
            mostRightNodeOfCur = currentNode.left;
            if (mostRightNodeOfCur != null) {
                //如果存在右节点，右节点 指向的不是自己（指第一次来到此节点）
                //一直向右
                while (mostRightNodeOfCur.right != null && mostRightNodeOfCur.right != currentNode) {
                    mostRightNodeOfCur = mostRightNodeOfCur.right;
                }
                //此时mostRightNodeOfCur 是左子树的最右节点
                //如果最右节点的右为null 说明是第一次来到此节点
                if (mostRightNodeOfCur.right == null) {
                    //让最右的右节点指向上一层
                    mostRightNodeOfCur.right = currentNode;
                    //自己向左
                    currentNode = currentNode.left;
                    continue;
                } else {
                    //第二次来到 让最右指向空
                    mostRightNodeOfCur.right = null;
                    //逆序打印当前节点左树右边界 这里需要先让mostRightNodeOfCur.right = null;
                    //不然会打印错误
                    reverseRightPrintThanReduction(currentNode.left);
                }
            }
            currentNode = currentNode.right;
        }
        //最后打印下整个树的右边界
        reverseRightPrintThanReduction(node);
    }


    /***
     * 逆序打印有边界并还原
     * @param node 当前节点
     */
    private static void reverseRightPrintThanReduction(TreeNode node) {
        TreeNode reverseNode = reverseRightEdge(node);
        TreeNode temp = reverseNode;
        while (temp != null) {
            System.out.print(temp.val + "\t");
            temp = temp.right;
        }
        reverseRightEdge(reverseNode);
    }

    /****
     * 翻转有边界节点的右指指针指向
     * @param from 你要翻转那个节点
     * @return 翻转后的新头节点
     */
    private static TreeNode reverseRightEdge(TreeNode from) {
        TreeNode preNode = null;
        TreeNode nextNode;
        while (from != null) {
            nextNode = from.right;
            from.right = preNode;
            preNode = from;
            from = nextNode;
        }
        return preNode;
    }


    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);

        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;

        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;

        treeNode3.left = treeNode6;
        treeNode3.right = treeNode7;


        morrisPrePrint(treeNode1);
        System.out.println();
        morrisMidPrint(treeNode1);
        System.out.println();
        morrisPostPrint(treeNode1);
    }
}
